The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(O(1), O(n^1)).

(0) Obligation:

Runtime Complexity TRS:
The TRS R consists of the following rules:

0(1(2(1(x1)))) → 1(2(1(1(0(1(2(0(1(2(x1))))))))))
0(1(2(1(x1)))) → 1(2(1(1(0(1(2(0(1(2(0(1(2(x1)))))))))))))
0(1(2(1(x1)))) → 1(2(1(1(0(1(2(0(1(2(0(1(2(0(1(2(x1))))))))))))))))
0(1(2(1(x1)))) → 1(2(1(1(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(x1)))))))))))))))))))
0(1(2(1(x1)))) → 1(2(1(1(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(0(1(2(x1))))))))))))))))))))))

Rewrite Strategy: INNERMOST

(1) CpxTrsMatchBoundsProof (EQUIVALENT transformation)

A linear upper bound on the runtime complexity of the TRS R could be shown with a Match Bound [MATCHBOUNDS1,MATCHBOUNDS2] of 2.
The certificate found is represented by the following graph.

Start state: 968
Accept states: [969]
Transitions:
968→969[0_1|0]
968→968[1_1|0, 2_1|0]
968→970[2_1|1]
968→979[2_1|1]
968→991[2_1|1]
968→1006[2_1|1]
968→1024[2_1|1]
970→971[1_1|1]
971→972[0_1|1]
972→973[2_1|1]
973→974[1_1|1]
974→975[0_1|1]
975→976[1_1|1]
976→977[1_1|1]
977→978[2_1|1]
978→969[1_1|1]
978→972[1_1|1]
978→981[1_1|1]
978→993[1_1|1]
978→1008[1_1|1]
978→1026[1_1|1]
978→1045[2_1|2]
978→1054[2_1|2]
978→1066[2_1|2]
978→1081[2_1|2]
978→1099[2_1|2]
979→980[1_1|1]
980→981[0_1|1]
981→982[2_1|1]
982→983[1_1|1]
983→984[0_1|1]
984→985[2_1|1]
985→986[1_1|1]
986→987[0_1|1]
987→988[1_1|1]
988→989[1_1|1]
989→990[2_1|1]
990→969[1_1|1]
990→972[1_1|1]
990→981[1_1|1]
990→993[1_1|1]
990→1008[1_1|1]
990→1026[1_1|1]
990→1045[2_1|2]
990→1054[2_1|2]
990→1066[2_1|2]
990→1081[2_1|2]
990→1099[2_1|2]
991→992[1_1|1]
992→993[0_1|1]
993→994[2_1|1]
994→995[1_1|1]
995→996[0_1|1]
996→997[2_1|1]
997→998[1_1|1]
998→999[0_1|1]
999→1000[2_1|1]
1000→1001[1_1|1]
1001→1002[0_1|1]
1002→1003[1_1|1]
1003→1004[1_1|1]
1004→1005[2_1|1]
1005→969[1_1|1]
1005→972[1_1|1]
1005→981[1_1|1]
1005→993[1_1|1]
1005→1008[1_1|1]
1005→1026[1_1|1]
1005→1045[2_1|2]
1005→1054[2_1|2]
1005→1066[2_1|2]
1005→1081[2_1|2]
1005→1099[2_1|2]
1006→1007[1_1|1]
1007→1008[0_1|1]
1008→1009[2_1|1]
1009→1010[1_1|1]
1010→1011[0_1|1]
1011→1012[2_1|1]
1012→1013[1_1|1]
1013→1014[0_1|1]
1014→1015[2_1|1]
1015→1016[1_1|1]
1016→1017[0_1|1]
1017→1018[2_1|1]
1018→1019[1_1|1]
1019→1020[0_1|1]
1020→1021[1_1|1]
1021→1022[1_1|1]
1022→1023[2_1|1]
1023→969[1_1|1]
1023→972[1_1|1]
1023→981[1_1|1]
1023→993[1_1|1]
1023→1008[1_1|1]
1023→1026[1_1|1]
1023→1045[2_1|2]
1023→1054[2_1|2]
1023→1066[2_1|2]
1023→1081[2_1|2]
1023→1099[2_1|2]
1024→1025[1_1|1]
1025→1026[0_1|1]
1026→1027[2_1|1]
1027→1028[1_1|1]
1028→1029[0_1|1]
1029→1030[2_1|1]
1030→1031[1_1|1]
1031→1032[0_1|1]
1032→1033[2_1|1]
1033→1034[1_1|1]
1034→1035[0_1|1]
1035→1036[2_1|1]
1036→1037[1_1|1]
1037→1038[0_1|1]
1038→1039[2_1|1]
1039→1040[1_1|1]
1040→1041[0_1|1]
1041→1042[1_1|1]
1042→1043[1_1|1]
1043→1044[2_1|1]
1044→969[1_1|1]
1044→972[1_1|1]
1044→981[1_1|1]
1044→993[1_1|1]
1044→1008[1_1|1]
1044→1026[1_1|1]
1044→1045[2_1|2]
1044→1054[2_1|2]
1044→1066[2_1|2]
1044→1081[2_1|2]
1044→1099[2_1|2]
1045→1046[1_1|2]
1046→1047[0_1|2]
1047→1048[2_1|2]
1048→1049[1_1|2]
1049→1050[0_1|2]
1050→1051[1_1|2]
1051→1052[1_1|2]
1052→1053[2_1|2]
1053→975[1_1|2]
1053→984[1_1|2]
1053→996[1_1|2]
1053→1011[1_1|2]
1053→1029[1_1|2]
1053→1120[2_1|2]
1053→1129[2_1|2]
1053→1141[2_1|2]
1053→1156[2_1|2]
1053→1174[2_1|2]
1054→1055[1_1|2]
1055→1056[0_1|2]
1056→1057[2_1|2]
1057→1058[1_1|2]
1058→1059[0_1|2]
1059→1060[2_1|2]
1060→1061[1_1|2]
1061→1062[0_1|2]
1062→1063[1_1|2]
1063→1064[1_1|2]
1064→1065[2_1|2]
1065→975[1_1|2]
1065→984[1_1|2]
1065→996[1_1|2]
1065→1011[1_1|2]
1065→1029[1_1|2]
1065→1120[2_1|2]
1065→1129[2_1|2]
1065→1141[2_1|2]
1065→1156[2_1|2]
1065→1174[2_1|2]
1066→1067[1_1|2]
1067→1068[0_1|2]
1068→1069[2_1|2]
1069→1070[1_1|2]
1070→1071[0_1|2]
1071→1072[2_1|2]
1072→1073[1_1|2]
1073→1074[0_1|2]
1074→1075[2_1|2]
1075→1076[1_1|2]
1076→1077[0_1|2]
1077→1078[1_1|2]
1078→1079[1_1|2]
1079→1080[2_1|2]
1080→975[1_1|2]
1080→984[1_1|2]
1080→996[1_1|2]
1080→1011[1_1|2]
1080→1029[1_1|2]
1080→1120[2_1|2]
1080→1129[2_1|2]
1080→1141[2_1|2]
1080→1156[2_1|2]
1080→1174[2_1|2]
1081→1082[1_1|2]
1082→1083[0_1|2]
1083→1084[2_1|2]
1084→1085[1_1|2]
1085→1086[0_1|2]
1086→1087[2_1|2]
1087→1088[1_1|2]
1088→1089[0_1|2]
1089→1090[2_1|2]
1090→1091[1_1|2]
1091→1092[0_1|2]
1092→1093[2_1|2]
1093→1094[1_1|2]
1094→1095[0_1|2]
1095→1096[1_1|2]
1096→1097[1_1|2]
1097→1098[2_1|2]
1098→975[1_1|2]
1098→984[1_1|2]
1098→996[1_1|2]
1098→1011[1_1|2]
1098→1029[1_1|2]
1098→1120[2_1|2]
1098→1129[2_1|2]
1098→1141[2_1|2]
1098→1156[2_1|2]
1098→1174[2_1|2]
1099→1100[1_1|2]
1100→1101[0_1|2]
1101→1102[2_1|2]
1102→1103[1_1|2]
1103→1104[0_1|2]
1104→1105[2_1|2]
1105→1106[1_1|2]
1106→1107[0_1|2]
1107→1108[2_1|2]
1108→1109[1_1|2]
1109→1110[0_1|2]
1110→1111[2_1|2]
1111→1112[1_1|2]
1112→1113[0_1|2]
1113→1114[2_1|2]
1114→1115[1_1|2]
1115→1116[0_1|2]
1116→1117[1_1|2]
1117→1118[1_1|2]
1118→1119[2_1|2]
1119→975[1_1|2]
1119→984[1_1|2]
1119→996[1_1|2]
1119→1011[1_1|2]
1119→1029[1_1|2]
1119→1120[2_1|2]
1119→1129[2_1|2]
1119→1141[2_1|2]
1119→1156[2_1|2]
1119→1174[2_1|2]
1120→1121[1_1|2]
1121→1122[0_1|2]
1122→1123[2_1|2]
1123→1124[1_1|2]
1124→1125[0_1|2]
1125→1126[1_1|2]
1126→1127[1_1|2]
1127→1128[2_1|2]
1128→987[1_1|2]
1128→999[1_1|2]
1128→1014[1_1|2]
1128→1032[1_1|2]
1128→1195[2_1|2]
1128→1204[2_1|2]
1128→1216[2_1|2]
1128→1231[2_1|2]
1128→1249[2_1|2]
1129→1130[1_1|2]
1130→1131[0_1|2]
1131→1132[2_1|2]
1132→1133[1_1|2]
1133→1134[0_1|2]
1134→1135[2_1|2]
1135→1136[1_1|2]
1136→1137[0_1|2]
1137→1138[1_1|2]
1138→1139[1_1|2]
1139→1140[2_1|2]
1140→987[1_1|2]
1140→999[1_1|2]
1140→1014[1_1|2]
1140→1032[1_1|2]
1140→1195[2_1|2]
1140→1204[2_1|2]
1140→1216[2_1|2]
1140→1231[2_1|2]
1140→1249[2_1|2]
1141→1142[1_1|2]
1142→1143[0_1|2]
1143→1144[2_1|2]
1144→1145[1_1|2]
1145→1146[0_1|2]
1146→1147[2_1|2]
1147→1148[1_1|2]
1148→1149[0_1|2]
1149→1150[2_1|2]
1150→1151[1_1|2]
1151→1152[0_1|2]
1152→1153[1_1|2]
1153→1154[1_1|2]
1154→1155[2_1|2]
1155→987[1_1|2]
1155→999[1_1|2]
1155→1014[1_1|2]
1155→1032[1_1|2]
1155→1195[2_1|2]
1155→1204[2_1|2]
1155→1216[2_1|2]
1155→1231[2_1|2]
1155→1249[2_1|2]
1156→1157[1_1|2]
1157→1158[0_1|2]
1158→1159[2_1|2]
1159→1160[1_1|2]
1160→1161[0_1|2]
1161→1162[2_1|2]
1162→1163[1_1|2]
1163→1164[0_1|2]
1164→1165[2_1|2]
1165→1166[1_1|2]
1166→1167[0_1|2]
1167→1168[2_1|2]
1168→1169[1_1|2]
1169→1170[0_1|2]
1170→1171[1_1|2]
1171→1172[1_1|2]
1172→1173[2_1|2]
1173→987[1_1|2]
1173→999[1_1|2]
1173→1014[1_1|2]
1173→1032[1_1|2]
1173→1195[2_1|2]
1173→1204[2_1|2]
1173→1216[2_1|2]
1173→1231[2_1|2]
1173→1249[2_1|2]
1174→1175[1_1|2]
1175→1176[0_1|2]
1176→1177[2_1|2]
1177→1178[1_1|2]
1178→1179[0_1|2]
1179→1180[2_1|2]
1180→1181[1_1|2]
1181→1182[0_1|2]
1182→1183[2_1|2]
1183→1184[1_1|2]
1184→1185[0_1|2]
1185→1186[2_1|2]
1186→1187[1_1|2]
1187→1188[0_1|2]
1188→1189[2_1|2]
1189→1190[1_1|2]
1190→1191[0_1|2]
1191→1192[1_1|2]
1192→1193[1_1|2]
1193→1194[2_1|2]
1194→987[1_1|2]
1194→999[1_1|2]
1194→1014[1_1|2]
1194→1032[1_1|2]
1194→1195[2_1|2]
1194→1204[2_1|2]
1194→1216[2_1|2]
1194→1231[2_1|2]
1194→1249[2_1|2]
1195→1196[1_1|2]
1196→1197[0_1|2]
1197→1198[2_1|2]
1198→1199[1_1|2]
1199→1200[0_1|2]
1200→1201[1_1|2]
1201→1202[1_1|2]
1202→1203[2_1|2]
1203→1002[1_1|2]
1203→1017[1_1|2]
1203→1035[1_1|2]
1203→1270[2_1|2]
1203→1279[2_1|2]
1203→1291[2_1|2]
1203→1306[2_1|2]
1203→1324[2_1|2]
1204→1205[1_1|2]
1205→1206[0_1|2]
1206→1207[2_1|2]
1207→1208[1_1|2]
1208→1209[0_1|2]
1209→1210[2_1|2]
1210→1211[1_1|2]
1211→1212[0_1|2]
1212→1213[1_1|2]
1213→1214[1_1|2]
1214→1215[2_1|2]
1215→1002[1_1|2]
1215→1017[1_1|2]
1215→1035[1_1|2]
1215→1270[2_1|2]
1215→1279[2_1|2]
1215→1291[2_1|2]
1215→1306[2_1|2]
1215→1324[2_1|2]
1216→1217[1_1|2]
1217→1218[0_1|2]
1218→1219[2_1|2]
1219→1220[1_1|2]
1220→1221[0_1|2]
1221→1222[2_1|2]
1222→1223[1_1|2]
1223→1224[0_1|2]
1224→1225[2_1|2]
1225→1226[1_1|2]
1226→1227[0_1|2]
1227→1228[1_1|2]
1228→1229[1_1|2]
1229→1230[2_1|2]
1230→1002[1_1|2]
1230→1017[1_1|2]
1230→1035[1_1|2]
1230→1270[2_1|2]
1230→1279[2_1|2]
1230→1291[2_1|2]
1230→1306[2_1|2]
1230→1324[2_1|2]
1231→1232[1_1|2]
1232→1233[0_1|2]
1233→1234[2_1|2]
1234→1235[1_1|2]
1235→1236[0_1|2]
1236→1237[2_1|2]
1237→1238[1_1|2]
1238→1239[0_1|2]
1239→1240[2_1|2]
1240→1241[1_1|2]
1241→1242[0_1|2]
1242→1243[2_1|2]
1243→1244[1_1|2]
1244→1245[0_1|2]
1245→1246[1_1|2]
1246→1247[1_1|2]
1247→1248[2_1|2]
1248→1002[1_1|2]
1248→1017[1_1|2]
1248→1035[1_1|2]
1248→1270[2_1|2]
1248→1279[2_1|2]
1248→1291[2_1|2]
1248→1306[2_1|2]
1248→1324[2_1|2]
1249→1250[1_1|2]
1250→1251[0_1|2]
1251→1252[2_1|2]
1252→1253[1_1|2]
1253→1254[0_1|2]
1254→1255[2_1|2]
1255→1256[1_1|2]
1256→1257[0_1|2]
1257→1258[2_1|2]
1258→1259[1_1|2]
1259→1260[0_1|2]
1260→1261[2_1|2]
1261→1262[1_1|2]
1262→1263[0_1|2]
1263→1264[2_1|2]
1264→1265[1_1|2]
1265→1266[0_1|2]
1266→1267[1_1|2]
1267→1268[1_1|2]
1268→1269[2_1|2]
1269→1002[1_1|2]
1269→1017[1_1|2]
1269→1035[1_1|2]
1269→1270[2_1|2]
1269→1279[2_1|2]
1269→1291[2_1|2]
1269→1306[2_1|2]
1269→1324[2_1|2]
1270→1271[1_1|2]
1271→1272[0_1|2]
1272→1273[2_1|2]
1273→1274[1_1|2]
1274→1275[0_1|2]
1275→1276[1_1|2]
1276→1277[1_1|2]
1277→1278[2_1|2]
1278→1020[1_1|2]
1278→1038[1_1|2]
1278→1345[2_1|2]
1278→1354[2_1|2]
1278→1366[2_1|2]
1278→1381[2_1|2]
1278→1399[2_1|2]
1279→1280[1_1|2]
1280→1281[0_1|2]
1281→1282[2_1|2]
1282→1283[1_1|2]
1283→1284[0_1|2]
1284→1285[2_1|2]
1285→1286[1_1|2]
1286→1287[0_1|2]
1287→1288[1_1|2]
1288→1289[1_1|2]
1289→1290[2_1|2]
1290→1020[1_1|2]
1290→1038[1_1|2]
1290→1345[2_1|2]
1290→1354[2_1|2]
1290→1366[2_1|2]
1290→1381[2_1|2]
1290→1399[2_1|2]
1291→1292[1_1|2]
1292→1293[0_1|2]
1293→1294[2_1|2]
1294→1295[1_1|2]
1295→1296[0_1|2]
1296→1297[2_1|2]
1297→1298[1_1|2]
1298→1299[0_1|2]
1299→1300[2_1|2]
1300→1301[1_1|2]
1301→1302[0_1|2]
1302→1303[1_1|2]
1303→1304[1_1|2]
1304→1305[2_1|2]
1305→1020[1_1|2]
1305→1038[1_1|2]
1305→1345[2_1|2]
1305→1354[2_1|2]
1305→1366[2_1|2]
1305→1381[2_1|2]
1305→1399[2_1|2]
1306→1307[1_1|2]
1307→1308[0_1|2]
1308→1309[2_1|2]
1309→1310[1_1|2]
1310→1311[0_1|2]
1311→1312[2_1|2]
1312→1313[1_1|2]
1313→1314[0_1|2]
1314→1315[2_1|2]
1315→1316[1_1|2]
1316→1317[0_1|2]
1317→1318[2_1|2]
1318→1319[1_1|2]
1319→1320[0_1|2]
1320→1321[1_1|2]
1321→1322[1_1|2]
1322→1323[2_1|2]
1323→1020[1_1|2]
1323→1038[1_1|2]
1323→1345[2_1|2]
1323→1354[2_1|2]
1323→1366[2_1|2]
1323→1381[2_1|2]
1323→1399[2_1|2]
1324→1325[1_1|2]
1325→1326[0_1|2]
1326→1327[2_1|2]
1327→1328[1_1|2]
1328→1329[0_1|2]
1329→1330[2_1|2]
1330→1331[1_1|2]
1331→1332[0_1|2]
1332→1333[2_1|2]
1333→1334[1_1|2]
1334→1335[0_1|2]
1335→1336[2_1|2]
1336→1337[1_1|2]
1337→1338[0_1|2]
1338→1339[2_1|2]
1339→1340[1_1|2]
1340→1341[0_1|2]
1341→1342[1_1|2]
1342→1343[1_1|2]
1343→1344[2_1|2]
1344→1020[1_1|2]
1344→1038[1_1|2]
1344→1345[2_1|2]
1344→1354[2_1|2]
1344→1366[2_1|2]
1344→1381[2_1|2]
1344→1399[2_1|2]
1345→1346[1_1|2]
1346→1347[0_1|2]
1347→1348[2_1|2]
1348→1349[1_1|2]
1349→1350[0_1|2]
1350→1351[1_1|2]
1351→1352[1_1|2]
1352→1353[2_1|2]
1353→1041[1_1|2]
1354→1355[1_1|2]
1355→1356[0_1|2]
1356→1357[2_1|2]
1357→1358[1_1|2]
1358→1359[0_1|2]
1359→1360[2_1|2]
1360→1361[1_1|2]
1361→1362[0_1|2]
1362→1363[1_1|2]
1363→1364[1_1|2]
1364→1365[2_1|2]
1365→1041[1_1|2]
1366→1367[1_1|2]
1367→1368[0_1|2]
1368→1369[2_1|2]
1369→1370[1_1|2]
1370→1371[0_1|2]
1371→1372[2_1|2]
1372→1373[1_1|2]
1373→1374[0_1|2]
1374→1375[2_1|2]
1375→1376[1_1|2]
1376→1377[0_1|2]
1377→1378[1_1|2]
1378→1379[1_1|2]
1379→1380[2_1|2]
1380→1041[1_1|2]
1381→1382[1_1|2]
1382→1383[0_1|2]
1383→1384[2_1|2]
1384→1385[1_1|2]
1385→1386[0_1|2]
1386→1387[2_1|2]
1387→1388[1_1|2]
1388→1389[0_1|2]
1389→1390[2_1|2]
1390→1391[1_1|2]
1391→1392[0_1|2]
1392→1393[2_1|2]
1393→1394[1_1|2]
1394→1395[0_1|2]
1395→1396[1_1|2]
1396→1397[1_1|2]
1397→1398[2_1|2]
1398→1041[1_1|2]
1399→1400[1_1|2]
1400→1401[0_1|2]
1401→1402[2_1|2]
1402→1403[1_1|2]
1403→1404[0_1|2]
1404→1405[2_1|2]
1405→1406[1_1|2]
1406→1407[0_1|2]
1407→1408[2_1|2]
1408→1409[1_1|2]
1409→1410[0_1|2]
1410→1411[2_1|2]
1411→1412[1_1|2]
1412→1413[0_1|2]
1413→1414[2_1|2]
1414→1415[1_1|2]
1415→1416[0_1|2]
1416→1417[1_1|2]
1417→1418[1_1|2]
1418→1419[2_1|2]
1419→1041[1_1|2]

(2) BOUNDS(O(1), O(n^1))